Combination Sum IV

Question

None

Example 1

Input: nums = [1,2,3], target = 4
Output: 7

Solution

▭

all//Combination Sum IV.py

def combinationSum4(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1

    for i in range(target + 1):
        for num in nums:
            if num <= i:
                dp[i] += dp[i - num]

    return dp[target]

▯

all//Combination Sum IV.py

def combinationSum4(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1

    for i in range(target + 1):
        for num in nums:
            if num <= i:
                dp[i] += dp[i - num]

    return dp[target]